Reduce to One (REDONE)

You have become good friends with Chef. Right now, Chef is busy in the kitchen, so he asked you to solve a problem for him.

Consider a list of integers L. Initially L contains the integers 1 through n, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in L is not important. You should perform the following operation n – 1 times:

· Choose two elements of the list, let's denote them by x and y. These two elements may be equal.

· Erase the chosen elements from L.

· Append the number x + y + x * y to L.

At the end, L contains exactly one integer. Find the maximum possible value of this integer. Since the answer may be large, compute it modulo 1,000,000,007 (10⁹ + 7).

Input. The first line contains a single integer t denoting the number of test cases. The description of t test cases follows. The first and only line of each test case contains a single integer n (1 ≤ n ≤ 10⁶).

Output. For each test case, print a single line containing one integer – the maximum possible value of the final number in the list modulo 10⁹ + 7.

Sample input	Sample output
3 1 2 4	1 5 119

РЕШЕНИЕ

математика

Анализ алгоритма

Два числа x и y заменяются на (x + 1) * (y + 1) – 1.

Пусть L = {x, y, z}. Удалив x и y, получим L = {(x + 1) * (y + 1) – 1, z}. Удалив последние два числа, получим L = {(x + 1) * (y + 1) * (z + 1) – 1}.

Если L = {1, 2, …, n}, то в конце преобразований получим

L = {(1 + 1) * (2 + 1) * … * (n + 1) – 1} = {(n + 1)! – 1}

Реализация алгоритма

#include <stdio.h>

#define MOD 1000000007

#define MAX 1000002

long long p[MAX];

int n, i, tests;

int main(void)

{

scanf("%d", &tests);

p[1] = 1;

for (i = 2; i < MAX; i++)

p[i] = (p[i - 1] * i) % MOD;

while (tests--)

{

scanf("%d", &n);

printf("%lld\n", p[n + 1] - 1);

}

return 0;

}